Iterative Computation of Security Strategies of Matrix Games with Growing Action Set

摘要

This paper studies how to efficiently update the saddle-point strategy, orsecurity strategy of one player in a matrix game when the other player developsnew actions in the game. It is well known that the saddle-point strategy of oneplayer can be computed by solving a linear program. Developing a new actionwill add a new constraint to the existing LP. Therefore, our problem becomeshow to solve the new LP with a new constraint efficiently. Considering thepotentially huge number of constraints, which corresponds to the large size ofthe other player's action set, we use shadow vertex simplex method, whosecomputational complexity is lower than linear with respect to the size of theconstraints, as the basis of our iterative algorithm. We first rebuild the maintheorems in shadow vertex method with relaxed assumption to make sure suchmethod works well in our model, then analyze the probability that the oldoptimum remains optimal in the new LP, and finally provides the iterativeshadow vertex method whose computational complexity is shown to be strictlyless than that of shadow vertex method. The simulation results demonstrates ourmain results about the probability of re-computing the optimum and thecomputational complexity of the iterative shadow vertex method.